/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 //开辟数组，排序数组
 //赋值
// class Solution {
// public:
//     ListNode* sortList(ListNode* head) {
//         vector<int> nums;
//         for (ListNode* cur = head; cur; cur = cur->next)
//             nums.push_back(cur->val);

//         sort(nums.begin(), nums.end());
//         int i = 0;
//         for (ListNode* cur = head; cur; i++, cur = cur->next)
//             cur->val = nums[i];

//         return head;
//     }
// };

//递归，归并排序
// class Solution {
//     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//         ListNode* newHead = new ListNode;
//         ListNode* curA = list1;
//         ListNode* curB = list2;
//         ListNode* cur = newHead;

//         while (curA && curB)
//         {
//             if (curA->val <= curB->val)
//             {
//                 cur->next = curA;
//                 curA = curA->next;
//             }
//             else
//             {
//                 cur->next = curB;
//                 curB = curB->next;
//             }
//             cur = cur->next;
//         }

//         cur->next = curA ? curA : curB;
            
//         ListNode* head = newHead->next;
//         delete newHead;
//         return head;
//     }
//     ListNode* sortList(ListNode* left, ListNode* right)
//     {
//         if (!left)
//         {   
//             return left;
//         }
            
//         if (left->next == nullptr)
//             return left;

//         //找到中间节点
//         ListNode* slow = left;
//         ListNode* fast = left;
//         ListNode* prev;
//         while (fast && fast->next)
//         {
//             prev = slow;
//             slow = slow->next;
//             fast = fast->next->next;
//         }
//         prev->next = nullptr;
//         ListNode* list1 = sortList(left, nullptr);
//         ListNode* list2 = sortList(slow, nullptr);

//         return mergeTwoLists(list1, list2);
//     }
// public:
//     ListNode* sortList(ListNode* head) {
//         if (!head)
//             return head;
//         return sortList(head, nullptr);
//     }
// };

//非递归
class Solution {
    //合并两个有序链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newHead = new ListNode;
        ListNode* curA = list1;
        ListNode* curB = list2;
        ListNode* cur = newHead;

        while (curA && curB)
        {
            if (curA->val <= curB->val)
            {
                cur->next = curA;
                curA = curA->next;
            }
            else
            {
                cur->next = curB;
                curB = curB->next;
            }
            cur = cur->next;
        }

        cur->next = curA ? curA : curB;
            
        ListNode* head = newHead->next;
        delete newHead;
        return head;
    }
    //求得链表长度
    int listSize(ListNode* head)
    {
        int ret = 0;
        for (ListNode* cur = head; cur; cur = cur->next)
            ret++;
        
        return ret;
    }

    //断链cut
    //删除以head为头的链表的前n个节点，并返回剩余节点的头
    ListNode* cut(ListNode* head, int n)
    {
        ListNode* cur = head;
        while (--n && cur)
            cur = cur->next;

        if (cur == nullptr)
            return nullptr;
        
        ListNode* Next = cur->next;
        cur->next = nullptr;
        return Next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head)
            return head;
        
        int len = listSize(head);
        ListNode* newHead = new ListNode(0, head);
        
        for (int gap = 1; gap < len; gap *= 2)
        {
            ListNode* cur = newHead->next;
            ListNode* tail = newHead;
            while (cur)
            {
                ListNode* left = cur;// left->@->@->@->@->@->@->null
                ListNode* right = cut(left, gap);// left->@->@->null   right->@->@->@->@->null
                cur = cut(right, gap);// left->@->@->null   right->@->@->null   current->@->@->null

                tail->next = mergeTwoLists(left, right);// dummy.next -> @->@->@->@->null，最后一个节点是 tail，始终记录
                while (tail->next)
                    tail = tail->next;
            }
        }

        return newHead->next;
    }
};